Jump to content

BPL (complexity)

From Wikipedia, the free encyclopedia

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space),[1] sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time),[2] is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.

Error model

[edit]

The probabilistic Turing machines in the definition of BPL may only accept or reject incorrectly less than 1/3 of the time; this is called two-sided error. The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice. This error can be made 2p(x) times smaller for any polynomial p(x) without using more than polynomial time or logarithmic space by running the algorithm repeatedly.

[edit]

Since two-sided error is more general than one-sided error, RL and its complement co-RL are contained in BPL. BPL is also contained in PL, which is similar except that the error bound is 1/2, instead of a constant less than 1/2; like the class PP, the class PL is less practical because it may require a large number of rounds to reduce the error probability to a small constant.

Nisan (1994) showed the weak derandomization result that BPL is contained in SC.[3] SC is the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, this result shows that, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.

BPL is contained in NC and in L/poly. Saks and Zhou showed that BPL is contained in DSPACE(log3/2 n),[4] and in 2021 Hoza improved this to show BPL is contained in DSPACE .[5]

References

[edit]
  1. ^ "Complexity Zoo: BPL". Archived from the original on 2012-08-05. Retrieved 2011-10-04.
  2. ^ Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M. (1989), "Two applications of inductive counting for complementation problems", SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1.1.394.1662, doi:10.1137/0218038
  3. ^ Nisan, N. (1994), "RL ⊆ SC", Computational Complexity, 4 (1): 1–11, doi:10.1007/BF01205052, An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing
  4. ^ Complexity theory lecture notes
  5. ^ Hoza, William (2021). "Better Pseudodistributions and Derandomization for Space-Bounded Computation".